"""
实现一个蚂蚁在时钟上从12点出发，每次可以顺时针或逆时针走一个刻度，总共走n步，问最终刚好回到12点的走法有多少种。
"""

class Soluction:
    def ant_clock_paths_dp(self,n):
        """
        使用动态规划计算走法数量
        """
        if n % 2 != 0:
            return 0

        # dp[i][j] 表示走i步后到达位置j的走法数量
        # 由于对称性，我们只需要考虑非负位置
        max_position = n
        dp = [[0] * (max_position + 1) for _ in range(n + 1)]

        # 初始状态：0步时在位置0有1种走法
        dp[0][0] = 1

        for step in range(1, n + 1):
            for position in range(max_position + 1):
                # 可以从position-1（顺时针）或position+1（逆时针）走来
                ways = 0
                if position - 1 >= 0:
                    ways += dp[step - 1][position - 1]  # 上一步在position-1，顺时针走一步
                if position + 1 <= max_position:
                    ways += dp[step - 1][position + 1]  # 上一步在position+1，逆时针走一步
                dp[step][position] = ways

        return dp[n][0]

    # 验证两种方法结果一致
    def verify_methods(self,max_n=10):
        print("验证组合数学和动态规划方法的一致性:")
        print("步数 | 组合数学 | 动态规划")
        print("-" * 35)

        for n in range(0, max_n + 1):
            comb_result = self.ant_clock_paths(n)
            dp_result = self.ant_clock_paths_dp(n)
            status = "✓" if comb_result == dp_result else "✗"
            print(f"{n:4} | {comb_result:8} | {dp_result:8} {status}")

    # 方法三：递归方法（教学用途，效率低）
    def ant_clock_paths_recursive(self,n, position=0):
        """
        递归方法计算走法数量（仅用于小规模n）
        """
        if n == 0:
            return 1 if position == 0 else 0

        # 分别尝试顺时针和逆时针走法
        clockwise = self.ant_clock_paths_recursive(n - 1, position - 1)
        counter_clockwise = self.ant_clock_paths_recursive(n - 1, position + 1)

        return clockwise + counter_clockwise

    # 完整演示
if __name__ == '__main__':
    print("=== 蚂蚁时钟问题演示 ===\n")

    # 测试不同步数
    steps_to_test = [0, 2, 4, 6, 8, 10]

    for n in steps_to_test:
        paths = Soluction().ant_clock_paths_dp(n)
        print(f"走 {n} 步后回到12点的走法数量: {paths}")

        # 解释为什么是这个结果
        if n % 2 == 0:
            k = n // 2
            print(f"  解释: 需要 {k} 步顺时针和 {k} 步逆时针")
            print(f"        组合数 C({n}, {k}) = {paths}")
        print()